package main

func IntSliceSplit(slice []int, start, end int) (src, des []int) {
	if len(slice) == 0 {
		return
	}
	if end > len(slice) {
		end = len(slice)
	}
	if start < 0 {
		start = 0
	}
	des = append(des, slice[start:end]...)
	src = append(src, slice[0:start]...)
	src = append(src, slice[end:len(slice)]...)
	return
}

func IntSliceInsert(slice []int, val int, idx int) []int {
	emptySlice := make([]int, 0)
	rear := append(emptySlice, slice[idx:]...)
	slice = append(slice[0:idx], val)
	slice = append(slice, rear...)
	return slice
}

func search(arr []int, num int) [][]int {
	result := make([][]int, 0)
	if len(arr) == num {
		result = append(result, arr)
	} else {
		makeCount := len(arr) - num + 1
		for i := 0; i < makeCount; i++ {
			if num > 1 {
				split, _ := IntSliceSplit(arr, 0, i+1)
				childCm := search(split, num-1)
				for _, v := range childCm {
					v = IntSliceInsert(v, arr[i], 0)
					result = append(result, v)
				}
			} else if num == 1 {
				result = append(result, []int{arr[i]})
			}
		}
	}
	return result
}

// =====================================================================

func ArrySliceSplit(slice [][]int, start, end int) (src, des [][]int) {
	if len(slice) == 0 {
		return
	}
	if end > len(slice) {
		end = len(slice)
	}
	if start < 0 {
		start = 0
	}
	des = append(des, slice[start:end]...)
	src = append(src, slice[0:start]...)
	src = append(src, slice[end:len(slice)]...)
	return
}

func ArrySliceInsert(slice [][]int, val []int, idx int) [][]int {
	emptySlice := make([][]int, 0)
	rear := append(emptySlice, slice[idx:]...)
	slice = append(slice[0:idx], val)
	slice = append(slice, rear...)
	return slice
}

func search2(arr [][]int, num int) [][][]int {
	result := make([][][]int, 0)
	if len(arr) == num {
		result = append(result, arr)
	} else {
		makeCount := len(arr) - num + 1
		for i := 0; i < makeCount; i++ {
			if num > 1 {
				split, _ := ArrySliceSplit(arr, 0, i+1)
				childCm := search2(split, num-1)
				for _, v := range childCm {
					v = ArrySliceInsert(v, arr[i], 0)
					result = append(result, v)
				}
			} else if num == 1 {
				result = append(result, [][]int{arr[i]})
			}
		}
	}
	return result
}
